package ch.ethz.fcl.metrobuzz.algorithm.network.shortest_path.public_transport;

import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

import ch.ethz.fcl.metrobuzz.MBProperty;
import ch.ethz.fcl.metrobuzz.data.MBData;
import ch.ethz.fcl.metrobuzz.data.scene.basemap.Edge;
import ch.ethz.fcl.metrobuzz.data.scene.basemap.Node;
import ch.ethz.fcl.metrobuzz.data.transit.Stop;
import ch.ethz.fcl.metrobuzz.data.transit.TransitRoute;

/**
 * Dijkstra algorithm implemented for find all paths from one stop to all other
 * stops
 * 
 * @author Zeng Wei
 * @email zeng@arch.ethz.ch
 * 
 */
public class OneToAllDijkstraPublic {
	private MBData data;

	private Map<Stop, Integer> visitedStopsMap;
	// records path from source to all stops
	private Map<Stop, PathPublic> pathMap;

	private TreeSet<Stop> pathTreeSet;

	private Map<String, Integer> visitedTransitRouteStop;

	public OneToAllDijkstraPublic(MBData data) {
		this.data = data;
	}

	/**
	 * @param source
	 * @param timeLimit
	 * @return the shortest path from a node to all other nodes at current time
	 *         within the time limit
	 */
	public LinkedHashMap<Stop, PathPublic> getShortestPath(Stop source,
			float timeLimit) {
		pathMap = new HashMap<Stop, PathPublic>();

		pathTreeSet = new TreeSet<Stop>(new Comparator<Stop>() {
			@Override
			public int compare(Stop s1, Stop s2) {
				PathPublic p1 = pathMap.get(s1);
				PathPublic p2 = pathMap.get(s2);

				return p1.getCost() >= p2.getCost() ? 1 : -1;
			}
		});

		// sort paths according to the cost
		LinkedHashMap<Stop, PathPublic> sortedPathMap = new LinkedHashMap<Stop, PathPublic>();

		visitedTransitRouteStop = new HashMap<String, Integer>();

		visitedStopsMap = new HashMap<Stop, Integer>();

		PathPublic path = new PathPublic(data);
		pathMap.put(source, path);

		pathTreeSet.add(source);

		while (pathTreeSet.size() > 0) {
			Stop evaluationStop = pathTreeSet.pollFirst();

			// put into the sorted path so the cost always increase
			sortedPathMap.put(evaluationStop, pathMap.get(evaluationStop));
			evaluateNextStops(evaluationStop, timeLimit);

			// only evaluate nearby stops for accessibility project
			if (MBProperty.ACCESSIBILITY)
				evaluateNearbyStops(evaluationStop, timeLimit);

			visitedStopsMap.put(evaluationStop, 1);
		}

		return sortedPathMap;
	}

	/**
	 * put next stops accessible from evaluation stop according to public
	 * transport routings routings
	 * 
	 * @param evaluationStop
	 * @param timeLimit
	 */
	private void evaluateNextStops(Stop evaluationStop, float timeLimit) {
		PathPublic evaluatingPath = pathMap.get(evaluationStop);

		// if the evaluating path cost bigger than time limit, return
		if (evaluatingPath.getCost() >= timeLimit) {
			return;
		}

		List<TransitRoute> passingRoutes = evaluationStop.getPassingRoutes();

		// if (evaluationStop.getId().equals("22009"))
		// for (TransitRoute route : passingRoutes)
		// System.out.println("Evaluate stop " + evaluationStop.getId()
		// + " size " + passingRoutes.size() + " passing route "
		// + route.getId());

		for (TransitRoute route : passingRoutes) {
			// ignore if the route contains '-p' (after 24:00)
			if (route.getId().contains("-p"))
				continue;

			int comingPathRouteSize = evaluatingPath.getPath().size();
			boolean changeRoute = false;
			if (comingPathRouteSize == 0) {
				changeRoute = true;
			} else {
				TransitRoute lastRoute = evaluatingPath.getPath()
						.get(comingPathRouteSize - 1).getTransitRoute();
				if (lastRoute == null
						|| !lastRoute.getId().equals(route.getId()))
					changeRoute = true;
			}

			int stopIndex = route.getStopIndex(evaluationStop);
			List<Stop> allStops = route.getStops();
			if (stopIndex == -1 || stopIndex >= (allStops.size() - 1))
				continue;

			float newPathCost = 0;
			if (changeRoute) {
				int frequency = evaluationStop.getRouteFrequency(route,
						MBData.startTime, 1);
				if (frequency == 0) {
					// if bus, add waiting time 10 minutes
					if (route.getMode().equals("bus"))
						newPathCost += 6 * 60;

					// if MRT, add waiting time 3 minutes
					else
						newPathCost += 2 * 60;

				} else
					// add average waiting time
					newPathCost += (15 * 60 / frequency) / 2;
			}

			for (int i = stopIndex + 1; i < allStops.size(); i++) {
				Stop preStop = allStops.get(i - 1);
				Stop curStop = allStops.get(i);

				if (visitedTransitRouteStop
						.get(route.getId() + curStop.getId()) != null)
					break;

				visitedTransitRouteStop.put(route.getId() + curStop.getId(), 1);

				if (visitedStopsMap.get(curStop) != null)
					continue;

				// if the route is MRT
				if (!route.getMode().equals("bus")) {
					Node startNode = data.getScene().getNode(preStop.getId());
					Node endNode = data.getScene().getNode(curStop.getId());
					Edge e = data.getScene().getEdge(startNode, endNode);

					float speed = 40 / 3.6f;

					// if (route.getId().equals("EW_weeksatday_1"))
					// System.out.println(route.getId() + " " + " edge "
					// + e.getId() + " cost " + e.distance() / speed
					// + " path cost " + newPathCost);

					newPathCost += e.distance() / speed;
				} else {
					newPathCost += route.getCost(MBData.startTime, i - 1, i);

					// if (route.getId().equals("30_weekday_2"))
					// System.out.println(route.getId() + " from " + (i - 1)
					// + " to " + i + " cost "
					// + route.getCost(MBData.startTime, i - 1, i)
					// + " path cost " + newPathCost);
				}
				// add 20 seconds for boarding and alighting at each stop
				newPathCost += 20;

				if (evaluatingPath.getCost() + newPathCost > timeLimit)
					break;

				PathPublic nextPossiblePath = pathMap.get(curStop);

				// path to the next stop is not exist or the cost is
				// bigger than new path
				if (nextPossiblePath == null
						|| (nextPossiblePath.getCost() > evaluatingPath
								.getCost() + newPathCost)) {
					// create a new path for the stop
					PathPublic newPath = new PathPublic(data, evaluatingPath);

					newPath.addRoute(route, evaluationStop, curStop,
							newPathCost);

					pathMap.put(curStop, newPath);

					if (nextPossiblePath != null)
						pathTreeSet.remove(curStop);
					pathTreeSet.add(curStop);
				}
			}
		}
	}

	/**
	 * evaluate nearby stops accessible by walking
	 * 
	 * @param stop
	 */
	private void evaluateNearbyStops(Stop evaluationStop, float timeLimit) {
		PathPublic evaluatingPath = pathMap.get(evaluationStop);

		// if the evaluating path cost bigger than time limit, return
		if (evaluatingPath.getCost() >= timeLimit)
			return;

		Map<Stop, Float> closeStopMap = evaluationStop.getCloseStopsMap();

		// if last route is walk, stop evaluate
		if (evaluatingPath.getLastRoute() != null
				&& evaluatingPath.getLastRoute().getTransitRoute() == null)
			return;

		for (Stop closeStop : closeStopMap.keySet()) {
			float walkCost = closeStopMap.get(closeStop);

			if (evaluatingPath.getCost() + walkCost >= timeLimit)
				continue;

			if (closeStop.getId().equals("22489")
					&& evaluationStop.getId().equals("EW27"))
				continue;

			if (closeStop.getId().equals("EW27")
					&& evaluationStop.getId().equals("22489"))
				continue;

			if (closeStop.getId().equals("22481")
					&& evaluationStop.getId().equals("EW27"))
				continue;

			if (closeStop.getId().equals("EW27")
					&& evaluationStop.getId().equals("22481"))
				continue;

			PathPublic nextStopPath = pathMap.get(closeStop);

			if (nextStopPath == null
					|| (nextStopPath.getCost() > evaluatingPath.getCost()
							+ walkCost)) {
				// create a new path for the stop
				PathPublic newPath = new PathPublic(data, evaluatingPath);

				newPath.addRoute(null, evaluationStop, closeStop, walkCost);

				pathMap.put(closeStop, newPath);

				if (nextStopPath != null)
					pathTreeSet.remove(closeStop);

				pathTreeSet.add(closeStop);
			}
		}
	}
}
